package com.leetcode.algorithm.y22.m06;

/**
 * 1289. 下降路径最小和 II
 * 
 * https://leetcode.cn/problems/minimum-falling-path-sum-ii/
 * 
 * @author jie.deng
 *
 */
class Question1289Solution01 {

	public int minFallingPathSum(int[][] grid) {
		int rows = grid.length;
		int cols = grid[0].length;

		// DP状态定义:dp[i]表示截止第row行，以grid[row][i]为终点的下降路径最小和
		int[] dp = new int[cols];
		// 状态初始化
		for (int col = 0; col < cols; col++) {
			dp[col] = grid[0][col];
		}
		// 状态转移方程
		for (int row = 1; row < rows; row++) {
			// 截止上一行的最小值和最小值的索引
			int minNum = dp[0];
			int minIdx = 0;
			for (int col = 1; col < cols; col++) {
				if (dp[col] < minNum) {
					minNum = dp[col];
					minIdx = col;
				}
			}

			int minNumOther = Integer.MAX_VALUE;
			for (int col = 0; col < cols; col++) {
				if (col != minIdx && dp[col] < minNumOther) {
					minNumOther = dp[col];
				}
			}

			for (int col = 0; col < cols; col++) {
				dp[col] = grid[row][col] + (col == minIdx ? minNumOther : minNum);
			}
		}

		int minFallingPathSum = dp[0];
		for (int col = 1; col < cols; col++) {
			if (dp[col] < minFallingPathSum) {
				minFallingPathSum = dp[col];
			}
		}
		return minFallingPathSum;
	}

}